Establishing the starting boundary of a received message within the transport symbol stream is a common task in every wireless communication systems 100. As shown in FIG. 1, to this end, a transmitter 110 sends a special symbol sequence, the preamble, at the head of the message 120 proper; and in a receiver 130 the recovered preamble is stripped off the symbol stream and the rest is forwarded to message processing.
The full preamble, however, is never available to signal processing as an initial part of it is consumed by signal presence detection and AGC (Automatic/Adaptive Gain Control) settling. This together with other considerations leads to the universally adopted preamble structure: a multi-symbol preamble pattern (PP) repeated a number of (M) times immediately followed by a start-of-frame delimiter (SFD) sequence. Within receiver 130, search for the PP establishes a timing raster and finding the SFD starting at a raster point delimits the message start as shown in FIG. 2.
The signal available from the radio (after some preliminary processing) is the original preamble distorted by channel noise and carrier offset (carrier frequency difference between the transmitting and receiving devices). Direct matching is thus not possible; rather the correlation between segments of the input and the expected PP is computed. For the computation sampled versions of both signals are used, where the PP is represented as N samples.
The magnitude of the complex result provides a measure of similarity between the PP and the input segment currently processed. (Preamble patterns are designed to have good autocorrelation property.)
In principle, in order to find a sample position where a PP starts searches should be started at every preamble sample position as indicated in FIG. 3. The length of each search depends on how many, say K (<M) consecutive PPs do we want to use for making a decision. Searches that start N samples (the length of the PP) apart establish the same timing raster, i.e. find the same SFD provided at least one of them succeeds. These, we say, belong to the same search class 3100, 3101, 3102, etc. As can be seen in FIG. 3, there are N search classes 3100, 3101, 3102, . . . arbitrarily numbered 0 to N−1 counting from the start of the searching process. In a class there may be at most K active searches: one into its first N-sample segments, one into its first 2N-sample sequence etc.
During the searching process received preamble samples are shifted into a single N-sample correlator 320. It starts operating after the first N samples of the preamble have been shifted in. From then on at each shifting step it outputs the matching score for the sample sequence it is currently looking at and the number of the search class it belongs to.
It is implicitly assumed that the higher the score the better the match is and that the score for a longer sequence in a class is the sum of the scores for its constituent subsequences. The search strategies differ in the way the data available is used to arrive to a decision.
Devices implementing common wireless standards invariably use the simple rule: if the current matching score exceeds a preset threshold the PP is found and the timing raster is established. The rule works as standards are designed such that at noise levels this fails to locate the PP message processing would fail with high probability as well.
The assumption, however, cannot be applied universally. With advanced symbol coding and data error control techniques message decoding can be made to work at much lower S/N (Symbol-to-Noise Ratio) levels. These techniques are not available to preamble detection thus it is vitally important that all information available in the received, noisy preamble is fully utilized in order to match the improvement in the message processing part of reception. In other words, the worse the SNR and/or higher the required detection reliability is the longer the preamble segment used in the search must be. This technology requires an unacceptably high number of logic gates. For example, when using a 125 kb/s data rate, 3˜4 dB below the noise floor and in the presence of a large carrier offset, achieving a greater than 99.8% detection ratio requires a 5 preamble period search length. Considering that each preamble requires 8 symbols and each symbol requires 8 bit, results in a search length of 8*8*5=320 bit. In this example, implementing the textbook solution is estimated to consume about 50 k logic gates, which is, in many applications, an unacceptable size when compared to the silicon area available for the whole digital component.